package src.dp.bag01;

public class no1049 {//最后一块石头的重量II，与416一样，只是最后对dp[target]的处理方式不同

    /**
     * 1. dp数组下标含义：容量为 j 的背包，最多能装 dp[j] 重量(最后会剩下一块石头，即代表背包装不满，尽量装最多能装多少)，
     * 物品的重量为stones[i]，物品的价值也为stones[i]
     * 2. 递推公式：dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i] )
     * 3. 初始化数组：dp[j]都初始化为0
     * 4. 遍历顺序：先物品后背包，遍历背包时倒序
     */
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int num : stones) {
            sum += num;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];

        for (int i = 0; i < stones.length; i++) {
            for (int j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }

        //分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]
        //target = sum/2 因为是向下取整，所以sum - dp[target] 一定 >= dp[target]的
        //那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]
        return sum - dp[target] - dp[target];

    }
}
